package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/'>从二叉搜索树到更大和树(Binary Search Tree to Greater Sum Tree)</a>
 * <p>给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。</p>
 * <p>
 * 提醒一下， 二叉搜索树 满足下列约束条件：
 *     <ul>
 *         <li>节点的左子树仅包含键 小于 节点键的节点。</li>
 *         <li>节点的右子树仅包含键 大于 节点键的节点。</li>
 *         <li>左右子树也必须是二叉搜索树。</li>
 *     </ul>
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
 *                              4
 *                            /   \
 *                           1     6
 *                          / \   / \
 *                         0   2 5   7
 *                              \     \
 *                               3     8
 *      输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
 *
 * 示例 2：
 *      输入：root = [0,null,1]
 *      输出：[1,null,1]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>树中的节点数在 [1, 100] 范围内。</li>
 *      <li>0 <= Node.val <= 100</li>
 *      <li>树中的所有值均 不重复 。</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/22 15:02
 */
public class LC1038BinarySearchTreeToGreaterSumTree_M {

    static class Solution {
        int sum = 0;

        /**
         * // 反中序遍历：右根左
         */
        public TreeNode bstToGst(TreeNode root) {
            if (root == null) {
                return null;
            }
            // 递归右子树的节点和
            bstToGst(root.right);
            sum += root.val;
            // 更新节点的值
            root.val = sum;
            // 递归左子树
            bstToGst(root.left);
            return root;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(4);
        root1.left = new TreeNode(1);
        root1.left.left = new TreeNode(0);
        root1.left.right = new TreeNode(2);
        root1.left.right.right = new TreeNode(3);
        root1.right = new TreeNode(6);
        root1.right.left = new TreeNode(5);
        root1.right.right = new TreeNode(7);
        root1.right.right.right = new TreeNode(8);

        Solution solution = new Solution();
        TreeNode.printTree(solution.bstToGst(root1));
    }
}
